import java.util.Arrays;

public class Solution {
    public int[] twoSum(int[] price, int target) {
        Arrays.sort(price);

        int left = 0;
        int right = price.length - 1;

        while (left < right){
            int sum = price[left] + price[right];
            if (sum > target){
                right--;
            }else if (sum < target){
                left++;
            }else{
                return new int[]{price[left], price[right]};
            }
        }

        return null;
    }


    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int ret = 0;

        //定下c
        int n = nums.length;
        for (int i = n - 1; i >= 2; i--){
            int left = 0;
            int right = i - 1;

            while (left < right){
                if (nums[left] + nums[right] > nums[i]){
                    ret += right - left;
                    right--;
                }else{
                    left++;
                }
            }

        }

        return ret;
    }


    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int ret = 0;

        while (left < right){
            int v = Math.min(height[left], height[right]) * (right - left);
            ret = Math.max(ret, v);

            if (height[left] < height[right]){
                left++;
            }else{
                right--;
            }
        }

        return ret;
    }

}
